package My;


import com.sun.javaws.WinBrowserSupport;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.*;

public class BinaryTree {

    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        //E.right=H;
        return A;
    }

    public void preOrder(TreeNode root) {   //当用表来实现树的时候1:创建表一定放在函数外不然每次都会创建一个新表，最后回溯到只有第一个A;
        //                                                    2:或者利用表创建新的左右树，然后每次递归完addAll即可，add相当于打印；
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    /*//或者放全局变量就不要左右树了，直接添加就行  List<Character> ret=new ArrayList();
    public List<Character> inOrder(TreeNode root){
        List<Character> ret=new ArrayList();
        if(root==null){
            return ret;
        }
        List<Character> leftTree=inOrder(root.left);
        //相当于利用临时表，来给正式表添加数据，不然正式表每次递归创建的新表添加的数据会被回溯然后销毁
        //因为表这些不具备打印效果，只有添加最后总的打印;所以一般都要有临时表这些来执行
        //尤其顺序表连弹出功能都不具备，只能全部弄完打印;
        ret.addAll(leftTree);
        ret.add(root.val);
        List<Character> rightTree=inOrder(root.right);
        ret.addAll(rightTree);
        return ret;
    }*/
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    // public static num;
    public int size(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //num++; 这是全局变量实现;
        return size(root.left) + size(root.right) + 1;

    }

    // public static leftnum; 同类也可以全局变量实现
    public int getleftszie(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;  //leftnum++;
        }
        return getleftszie(root.left) + getleftszie(root.right);
    }

    public int getlevelsize(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getlevelsize(root.left, k - 1) + getlevelsize(root.right, k - 1);
    }

    public int gethigh(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftheigh = gethigh(root.left);//+1;
        int rightheigh = gethigh(root.right);//+1; 每次遍历相当于遍历一个结点或一个高度；
        return leftheigh >= rightheigh ? leftheigh + 1 : rightheigh + 1; //这里不加等号也可以因为＞反过来就是<=;
    }

    public TreeNode find(TreeNode root, char x) {
        if (root == null) {
            return null;
        }

        if (root.val == x) {
            return root;
        }
        TreeNode ret = find(root.left, x);
        if (ret != null) {
            return ret;
        }
        TreeNode ret2 = find(root.right, x);
        if (ret2 != null) {
            return ret2;
        }
        return null;
    }

    /* public void levelOrder(TreeNode root){  //非递归
         if(root==null){
             return;
         }
         Queue<TreeNode> queue=new LinkedList<>();
         queue.offer(root);
         while (!queue.isEmpty()){
             TreeNode cur=queue.poll();
             System.out.print(cur.val+" ");
             if(cur.left!=null){
                 queue.offer(cur.left);
             }
             if(cur.right!=null){
                 queue.offer(cur.right);
             }
         }
     }*/
    public List<List<Character>> levelOrder2(TreeNode root) {//非递归层序遍历
        List<List<Character>> ret = new ArrayList<>();
        if (root == null) return ret;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();//获取该层的元素个数然后放入表中//这里size放在外边不能更新，不然没办法表示行
            List<Character> list = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();//只要size不为空就出队列的一个元素然后放入表中，直到该层元素出完，出完以后队列中也刚好存好了下一层的元素
                list.add(cur.val);
                size--;//0
                if (cur.left != null) {//获取下一层的元素，以及存储个数在队列中
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(list);
            //相当于二维数组               [A]
            //                          [B C]
            //                          [D E F G]
            //                          [H]
            //整体是ret ，每一行是一个不同的list只不过名字相同而已但存储数据不同，因为每次都是new了个新的
        }
        return ret;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null) {
            return false;
        }
        if (p != null && q == null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public boolean isSubTree(TreeNode root, TreeNode subroot) { //判断是不是树的子树
        if (root == null) {
            return false;
        }
        if (isSameTree(root, subroot)) {
            return true;
        }
        if (isSameTree(root.left, subroot)) {
            return true;
        }
        if (isSameTree(root.right, subroot)) {
            return true;
        }
        return false;
    }

    public int height(TreeNode root) {//平衡二叉树一边求高度一边判断是不是平衡二叉树，比直接全部求完左右树然后判断abs《=1更加快速
        if (root == null) {
            return 0;
        }
        int leftH = height(root.left);
        int rightH = height(root.right);
        if (leftH >= 0 && rightH >= 0 && Math.abs(leftH - rightH) <= 1) {
            return Math.max(leftH, rightH) + 1;
        }
        return -1;
    }

    public boolean isBalanceTree(TreeNode root) {//判断是不是平衡二叉树 高度差《=1
        return height(root) >= 0;
    }

    public boolean isduicheng(TreeNode leftTree, TreeNode rightTree) {//判断两棵树是不是中心对称
        if (leftTree == null && rightTree != null) {
            return false;
        }
        if (rightTree == null && leftTree != null) {
            return false;
        }
        if (rightTree == null && rightTree == null) {
            return true;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }
        return isduicheng(leftTree.left, rightTree.right) && isduicheng(leftTree.right, rightTree.left);
    }

    public boolean zhongxingduicheng(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isduicheng(root.left, root.right); //判断一棵树是不是关于中心对称的原理就是写判断两颗树是不是中心对称，然后遍历树的左和右；
    }

    public boolean isCompleteTree(TreeNode root) { //判断是不是完全二叉树用层序遍历的思路
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        while (!queue.isEmpty()) {  //判断如果队列里全为null则是完全二叉树，否则则不是
            TreeNode cur = queue.peek();
            if (cur == null) {
                queue.poll();
            } else {
                return false;
            }
        }
        return true;
    }

    public static void preOrderIteration(TreeNode head) { //非递归前中后遍历用栈
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {//条件栈不为空即可
            TreeNode node = stack.pop();//没用即出栈打印
            System.out.print(node.val + " ");//前序先打印根，然后栈先放右再放左，边入栈边打印
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    public List<Character> preOrderIteration2(TreeNode root) { //非递归前中后遍历用栈和表
        List<Character> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {//不同于一个栈实现的是先全部入完左再入右，而一个栈是边入右边入左先打印根每次入完就弹出一个元素
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();//pop相当于删除调没用了回退时栈里不会再存在此数据
            cur = top.right;
        }
        return list;
    }

    public static void inOrderIteration(TreeNode head) {
        if (head == null) {
            return;
        }
        TreeNode cur = head;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            //中序先一直放左到底，然后打印看有没有右 //前序和中序区别就是入左时边入边打印是先序；
            //  入完再打印是中序；
            System.out.print(node.val + " ");
            if (node.right != null) {
                cur = node.right;
            }
        }
    }

    public List<Character> inOrderIteration2(TreeNode root) { //非递归前中后遍历用栈和表
        List<Character> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();//pop相当于删除调没用了回退时栈里不会再存在此数据
            list.add(top.val);
            //中序先一直放左到底，然后打印看有没有右
            // 前序和中序区别就是入左时边入边打印是先序,入完再打印是中序;
            cur = top.right;
        }
        return list;
    }

    public static void postOrderIteration(TreeNode head) {
        //后序用两个栈放入第一个栈中左右，第二个栈入栈就是右左中，出第二个栈就逆了过来
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(head);
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);
            if (node.left != null) {
                stack1.push(node.left);
            }
            if (node.right != null) {
                stack1.push(node.right);
            }
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().val + " ");
        }
    }
        public List<Character> postOrderIteration2 (TreeNode root) { //非递归前中后遍历用栈和表
        List<Character>list=new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while (cur!=null||!stack.isEmpty()) {
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top = stack.peek();//pop相当于删除掉没用了回退时栈里不会再存在此数据 而peek和pop类似但不是没用多用于判断
            if(top.right==null||top.right==prev){
                stack.pop();
                list.add(top.val);
                //后序遍历要么用两个栈一个中左右，另一个入它的出栈右左中；
                //要么用一个栈加一个prev，先peek判断当确定右为null或者为上一次入过的则再进行打印，这是与中序和前序的最大区别多了一个判断条件
                prev=top;
            }else {
                cur=top.right;
            }
        }
        return list;
    }
   TreeNode dfs(TreeNode r1, TreeNode r2) { //合并二叉树
       if(r1==null || r2==null) { // 如果 r1和r2中，只要有一个是null，函数就直接返回接在r1的左或右
           return r1==null? r2 : r1;
       }
       r1.val += r2.val;//让r1的值 等于  r1和r2的值累加，再递归的计算两颗树的左节点、右节点
       r1.left = dfs(r1.left,r2.left);
       r1.right = dfs(r1.right,r2.right);
       return r1;
   }
    public int widthOfBinaryTree(TreeNode root) { //求二叉树最大宽度1：改变结点的值为编号，最右减最左+1为宽度
        if (root == null) {
            return 0;
        }
        int res = 1;
        LinkedList<TreeNode> queue = new LinkedList<>();
        root.val = 1;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            res = Math.max(queue.peekLast().val - queue.peekFirst().val + 1, res);
            while (size-- > 0) {//先用后减
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    //cur.left.val = cur.val * 2 - 1; int类型的
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                   // cur.right.val = cur.val * 2;
                    queue.offer(cur.right);
                }
            }
        }
        return res;
    }
        public int widthOfBinaryTree2(TreeNode root) {
       //求二叉树最大宽度1：不改变结点的值为编号，但创建了个新队列来记录编号，最右减最左+1为宽度
            if (root == null) {
                return 0;
            }
            int res = 1;
            LinkedList<TreeNode> queue = new LinkedList<>();// 每一个操作都如影随形，保证一一对应
            LinkedList<Integer> idxQ = new LinkedList<>();
            queue.offer(root);
            idxQ.offer(1);
            while (!queue.isEmpty()) {
                int size = queue.size();
                res = Math.max(idxQ.peekLast() - idxQ.peekFirst() + 1, res);// 这里就可以记录二叉树的最大宽度了
                while (size-- > 0) {
                    TreeNode cur = queue.poll();
                    int idx = idxQ.poll();//原队列出那编号的队列也出
                    if (cur.left != null) {
                        queue.offer(cur.left);
                        idxQ.offer(idx * 2 - 1);//原入则编号对列也入2*i-1
                    }
                    if (cur.right != null) {
                        queue.offer(cur.right);
                        idxQ.offer(idx * 2);//原入则编号对列也入2*i
                    }
                }
            }
            return res;
        }
        public TreeNode commonancestor(TreeNode root,TreeNode p,TreeNode q) { //找root树下p和q最近那个公共祖先
            if (root == null) {
                return root;
            }
            if(root==q||root==p){
                return root;
            }
            TreeNode leftRet=commonancestor(root.left,p,q);
            TreeNode rightRet=commonancestor(root.right,p,q);
            if(leftRet!=null&&rightRet!=null){
                return root;
            }else if(leftRet!=null){
                return leftRet;
            }else if(rightRet!=null){
                return rightRet;
            }
            return null;
        }
        public boolean getpath(TreeNode root,TreeNode node,Stack<TreeNode> stack){//利用栈找要求结点的位置,并实现寻找公共祖先结点
       if(root==null){
           return false;
       }
       stack.push(root);
       if(root==node){
           return true;
       }
       boolean flg1=getpath(root.left,node,stack);
       if(flg1==true){
           return true;
       }
       boolean flg2=getpath(root.left,node,stack);
       if(flg2==true){
           return true;
       }
       stack.pop();
       return false;
   }
   public TreeNode commonancestor2(TreeNode root,TreeNode p,TreeNode q){
       Stack<TreeNode>stack1=new Stack<>();
       getpath(root,p,stack1);
       Stack<TreeNode>stack2=new Stack<>();
       getpath(root,q,stack2);
       int size1=stack1.size();
       int size2=stack2.size();
       if(size1>size2){
           int s=size1-size2;
           while (s!=0){
               stack1.pop();
               s--;
           }
       }else if(size2>size1){
           int s=size2-size1;
           while (s!=0){
               stack2.pop();
               s--;
           }
       }
       while (!stack1.empty()&&!stack2.empty()){
           if(stack1.peek()==stack2.peek()){
               return stack1.peek();
           }else {
               stack1.pop();
               stack2.pop();
           }
       }
       return null;
   }

    TreeNode prev=null;
   public void treeconvertlianbiaozhongxu(TreeNode root){//中序和后序实现链表的转换
       if(root==null){
           return;
       }
       treeconvertlianbiaozhongxu(root.left);
       root.left=prev;
       if(prev!=null){
           prev.right=root;
       }
       prev=root;
       treeconvertlianbiaozhongxu(root.right);
   }
   public TreeNode treeconvertlianbiaozhongxu2(TreeNode houxuroot){
       if(houxuroot==null){
           return null;
       }
       treeconvertlianbiaozhongxu(houxuroot);
       TreeNode head=houxuroot;
       while (head.left!=null){
           System.out.println(head.val);
           head=head.left;
       }
       return head;
   }
   /*
   public int preindex=0;
   public TreeNode build(int[]preorder,int[] inorder,int inbegin,int inend){
       if(inbegin>inend){
           return null;
       }
       TreeNode root=new TreeNode(preorder[preindex]);//根据前序和中序遍历的数组创建一个二叉树,核心都是中序遍历，前序作为引子;
       int rootindex=find(inorder,inbegin,inend,preorder[preindex]);
       preindex++; //后序postindex--;

       root.left=build(preorder,inorder,inbegin,rootindex-1);
       root.right=build(preorder,inorder,rootindex+1,inend);
       return root;
   }
   public int find(int[] inorder,int inbegin,int inend,int val){
       for(int i=inbegin;i<inend;i++){
           if(inorder[i]==val){
               return i;
           }
       }
       return -1;
   }
   public TreeNode buildtree(int[]preorder,int[] inorder){
   //中序和后序组成二叉树则令preindex=0变为postindexpostorder.length-1;
       return build(preorder,inorder,0,inorder.length-1)
   }*/

}
